//class Solution {
//public:
//
//    bool find(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
//    {
//        if (root == nullptr)
//        {
//            return false;
//        }
//
//        path.push(root);
//        if (root->val == x->val)
//        {
//            return true;
//        }
//
//        if (find(root->left, x, path))
//            return true;
//        if (find(root->right, x, path))
//            return true;
//
//        path.pop();
//
//        return false;
//    }
//
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        stack<TreeNode*> ppath, qpath;
//
//        find(root, p, ppath);
//        find(root, q, qpath);     
//
//        while (ppath.size() != qpath.size())
//        {
//            if (ppath.size() > qpath.size())
//                ppath.pop();
//            else 
//                qpath.pop();
//        }
//
//        while (ppath.top() != qpath.top())
//        {
//            ppath.pop();
//            qpath.pop();
//        }
//
//        return ppath.top();
//    }
//};
//

//class Solution {
//public:
//    vector<vector<int>> levelOrderBottom(TreeNode* root) {
//        vector<vector<int>> vv;
//
//        // if (root == nullptr) return vv;
//
//        // queue<int> q;
//        // q.push(root->val);
//
//        queue<TreeNode*> q;
//        int qlsize = 0;
//        if (root != nullptr) 
//        {
//            q.push(root);
//            qlsize = 1;
//        }
//
//        while (!q.empty())
//        {
//            vector<int> v;
//
//            for (int i = 0; i < qlsize; i ++ )
//            {
//                TreeNode* front = q.front();
//                q.pop();
//                v.push_back(front->val);
//
//                if (front->left)
//                    q.push(front->left);
//                if (front->right)
//                    q.push(front->right);
//            }
//
//            vv.push_back(v);
//            qlsize = q.size();
//        }
//
//        reverse(vv.begin(), vv.end());
//
//        return vv;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> vv;
//
//        // if (root == nullptr) return vv;
//
//        // queue<int> q;
//        // q.push(root->val);
//
//        queue<TreeNode*> q;
//        int qlsize = 0;
//        if (root != nullptr) 
//        {
//            q.push(root);
//            qlsize = 1;
//        }
//
//        while (!q.empty())
//        {
//            vector<int> v;
//
//            for (int i = 0; i < qlsize; i ++ )
//            {
//                TreeNode* front = q.front();
//                q.pop();
//                v.push_back(front->val);
//
//                if (front->left)
//                    q.push(front->left);
//                if (front->right)
//                    q.push(front->right);
//            }
//
//            vv.push_back(v);
//            qlsize = q.size();
//        }
//
//        return vv;
//    }
//};

//class Solution {
//public:
//    string tree2str(TreeNode* root) {
//        if (root == nullptr)
//        {
//            return string();
//        }
//
//        string str;
//
//        str += (to_string(root->val));
//
//        if (root->left != nullptr || root->right != nullptr)
//        {
//            str.push_back('(');
//            str += tree2str(root->left);
//            str.push_back(')');
//        }
//
//        if (root->right != nullptr)
//        {
//            str.push_back('(');
//            str += tree2str(root->right);
//            str.push_back(')');
//        }
//
//        return str;
//    }
//};

//#include <iostream>
//
//using namespace std;
//
//int main()
//{
//
//}


//#include <iostream>
//
//using namespace std;
//
//const int N = 100010;
//int a[N];
//
//int main()
//{
//    int n = 0;
//    cin >> n;
//    
//    for (int i = 0; i < n; i ++ ) cin >> a[i];
//    
//    int flag = 0;
//    if (a[1] < a[0]) flag = 0;
//    else flag = 1;
//    
//    int res = 0;
//    int i = 1;
//    
//    while (i < n)
//    {
//        if (flag)
//        {
//            while (i < n && a[i] >= a[i - 1])
//            {
//                i ++ ;
//            }
//            flag = 0;
//            res ++ ;
//        }
//        else 
//        {
//            while (i < n && a[i] <= a[i - 1])
//            {
//                i ++ ;
//            }
//            flag = 1;
//            res ++ ;
//        }
//    }
//    
//    cout << res << endl;
//    
//    return 0;
//}
